package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;

public class TreeCousins {

    public boolean isCousins(TreeNode root, int x, int y) {
        if (root.val == x || root.val == y) {
            return false;
        }
        // res[0]代表x的pid和level，res[1]代表x的pid和level
        int[][] res = new int[2][2];
        traverse(root, res, x, y, 1);
        return res[0][0] != res[1][0] && res[0][1] == res[1][1];
    }

    /**
     * 层序遍历
     */
    public void traverse(TreeNode root, int[][] res, int x, int y, int level) {
        if (root == null || (res[0][0] > 0 && res[1][0] > 0)) {
            return;
        }
        if (root.left != null) {
            if (root.left.val == x) {
                res[0][0] = root.val;
                res[0][1] = level + 1;
            } else if (root.left.val == y) {
                res[1][0] = root.val;
                res[1][1] = level + 1;
            }
            traverse(root.left, res, x, y, level + 1);
        }
        if (root.right != null) {
            if (root.right.val == x) {
                res[0][0] = root.val;
                res[0][1] = level + 1;
            } else if (root.right.val == y) {
                res[1][0] = root.val;
                res[1][1] = level + 1;
            }
            traverse(root.right, res, x, y, level + 1);
        }
    }
}
